package Algorithms.classic;

import java.util.LinkedList;

/**
 * Method Name：基数排序算法实现
 * Method Description: 用到队列实现<br>
 *
 * <p>creator：zhihui.zhou
 * <p>createTime：2018/12/29 17:07
 */
public class RadixSort {

    private static final int RADIX_DEFAULT = 10;


    public static void main(String[] args) {
        SortUtils.test(RadixSort::radixSort);
    }


    private static int[] radixSort(int[] array) {
        return radixSort(array, RADIX_DEFAULT);
    }


    private static int[] radixSort(int[] array, int radix) {
        if(array == null || array.length == 0) {
            return array;
        }
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] > max) {
                max = array[i];
            }
        }
        int maxLoopNum = (int) Math.ceil(Math.log(max) / Math.log(radix));
        LinkedList<Integer>[] nodeLists = new LinkedList[radix];
        for (int i = 0; i < radix; i++) {
            nodeLists[i] = new LinkedList<>();
        }
        for (int i = 0; i < maxLoopNum; i++) {
            int devide = (int) Math.pow(radix, i);
            for (int j = 0; j < array.length; j++) {
                int index = array[j] / devide % radix;
                nodeLists[index].offer(array[j]);
            }
            int index = 0;
            for (LinkedList<Integer> nodeList : nodeLists) {
                while(!nodeList.isEmpty()) {
                    array[index++] = nodeList.poll();
                }
            }
        }
        return array;
    }
}